Efficient list decoding beyond half a minimum distance for Reed-Solomon and Bose and Ray-Chaudhuri (i.e., BCH) codes were first devised in 1997 and later improved almost three decades after the inauguration of an efficient hard-decision decoding method. In particular, for a given Reed-Solomon code C(n,k,d), a Guruswami-Sudan decoding method corrects up to n (1−√{square root over (1−d/n)}) errors, which effectively achieves a Johnson bound, a general lower bound on the number of errors to be corrected under a polynomial time for any code. Koetter and Vardy showed a way to translate soft-decision reliability information provided by a channel into a multiplicity matrix that is directly involved in the Guruswami-Sudan method. The resulting method substantially outperforms the Guruswami-Sudan method. Koetter et al. introduced a computational technique, based upon re-encoding and coordinate transformation, that reduces the complexity of a bivariate interpolation procedure. Justesen derived a condition for successful decoding using the Koetter-Vardy method for soft-decision decoding by introducing a few assumptions. Lee and O'Sullivan devised an algebraic soft-decision decoder for Hermitian codes. The algebraic soft-decision decoder follows a path set out by Koetter and Vardy for Reed-Solomon codes while constructing a set of generators of a certain module from which a Q-polynomial is extracted using the Gröbner conversion method.
Augot and Couvreur extended the Guruswami-Sudan method to achieve q-ary Johnson bounds,
                    q        -        1            q        ⁢          n      ⁡              (                  1          -                                    1              -                                                q                                      q                    -                    1                                                  ⁢                                  d                  n                                                                    )              ,for subfield subcodes of Reed-Solomon codes by distributing multiplicities across an alphabet of the q-ary subfield. However, the authors give only an asymptotic proof and fail to provide explicitly the minimum multiplicities to achieve the Johnson bound. Wu presented a new list decoding method (i.e., Wu method) for Reed-Solomon and binary BCH codes. The Wu method casts the list decoding as a rational curve fitting problem utilizing the polynomials constructed by the Berlekamp-Massey method. The Wu method achieves the Johnson bound for both Reed-Solomon and binary BCH codes. Beelen showed that the Wu method can be modified to achieve the binary Johnson bound for binary Goppa codes. We also showed that when a part of the positions are pre-corrected, the Wu method “neglects” the corrected positions and subsequently exhibits a larger list error correction capability (i.e., LECC) with smaller effective code length. A scenario of partial pre-correction is during the iterative decoding of product codes, where each row (column) component word is partially corrected by the preceding column (row) decoding, herein miscorrection is ignored. Pyndiah demonstrated that the iterative decoding of product codes achieves a near Shannon limit.
It would be desirable to implement a combined Koetter-Vardy and Chase decoding of cyclic codes.